package top.ivansong92.example.leetcode.learning.data.struct.array;

public class BinarySearch {

    public static void main(String[] args) {
        for(int i = 1; i < 28; i ++) {
            System.out.println(i + ":" +search(new int[]{1,4,6,9, 13,27}, i));
        }

    }

    public static int search(int[] array, int target) {
        if (array == null || array.length == 0
                || array[0] > target
                || array[array.length - 1] < target) {
            return -1;
        }

        if (array[0] == target) {
            return 0;
        }

        if (array[array.length - 1] == target) {
            return array.length - 1;
        }

        int mid = array.length / 2;
        int midVal = array[mid];
        if (target == midVal) {
            return mid;
        } else if (target > midVal) {
            return binarySearch(array, mid + 1, array.length - 2, target);
        } else {
            return binarySearch(array, 1, mid - 1, target);
        }
    }
    private static int binarySearch(int[] array, int start, int end, int target) {
        if (start > end || array[start] > target || array[end] < target) {
            return -1;
        }

        if (array[start] == target) {
            return start;
        }

        if (array[end] == target) {
            return end;
        }

        if (start == end) {
            return -1;
        }

        int mid = start / 2 + end / 2;
        int midVal = array[mid];
        if (target == midVal) {
            return mid;
        } else if (target > midVal) {
            return binarySearch(array, mid + 1, end - 1, target);
        } else {
            return binarySearch(array, start + 1, mid - 1, target);
        }
    }

}
